home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / jcool01.zip / BIGNUM.C < prev    next >
C/C++ Source or Header  |  1992-08-12  |  49KB  |  1,290 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. //
  13. // Created: MBN 11/01/89 -- Initial implementation
  14. // Updated: CLJ 04/19/90 -- Finished initial implementation of all functions
  15. // Updated: MJF 05/24/90 -- Added group names to RAISE
  16. // Updated: MJF 07/31/90 -- Added terse print
  17. // Updated: DAN 01/08/91 -- Fixed bug in add and multiply_aux
  18. // Updated: MJF 01/17/91 -- Fixed delete operations
  19. // Updated: MJF 01/21/91 -- Fixed multiply_aux, divide_aux and left_shift
  20. // Updated: DLS 03/22/91 -- New lite version
  21. // Updated: JAM 08/12/92 -- removed DOS specifics, stdized #includes
  22. // Updated: JAM 08/12/92 -- anach. form() replaced with iomanips
  23. // Updated: JAM 08/12/92 -- added DBLRET_HACK in CoolBigNum(double)
  24. // Updated: JAM 08/12/92 -- fixed(?) normalize() bug where 1 was being added
  25. //                          to dividend Data which could cause it to wrap to 0
  26. //
  27. // The Bignum class implements  infinite precision integers  and arithmetic.  A
  28. // Bignum  object storage  will grow and  shrink  in 16-bit chunks as necessary
  29. // based upon  its current value.   Implicit  conversion to the  system defined
  30. // types short, int, long,  float, and  double is supported by virtual operator
  31. // member functions from   the  base Number   class.  Addition  and subtraction
  32. // operations are performed by simple bitwise addition or subtraction on 32-bit
  33. // boundaries with checks for carry flag propagation.   The  multiplication and
  34. // division  operations  utilize  the algorithms   from  Knuth  Volume  2   for
  35. // efficiency. However, the user is  warned that the  Bignum integer arithmetic
  36. // class is still considerably slower than the built-in integer data types.
  37. //
  38.  
  39. #ifndef BIGNUMH                    // If no definition for class
  40. #include <cool/Bignum.h>            // include definition file
  41. #endif
  42.  
  43. #include <string.h>        // Include standard strings
  44. #define C_STRINGH
  45.  
  46. #include <math.h>        // Include the standard math library
  47. #include <ctype.h>        // Include character macros
  48. #include <stdlib.h>        // Include standard c library support
  49. #include <limits.h>        // for CHAR_BIT
  50.  
  51. #include <iomanip.h>          // Include stream maniplutors (eg, hex, setw)
  52.  
  53. int CoolBignum_Init::count;            
  54. int    data_bits_s;                // Initialize to 0 by default
  55. long   radix_s;    
  56.  
  57. CoolBignum zero_s;                // There is only 1 set of
  58. CoolBignum one_s;                // these Bignums
  59. CoolBignum eight_s;                
  60. CoolBignum ten_s;                // Constructors are called 
  61. CoolBignum sixteen_s;                // for static libraries.
  62. CoolBignum max_short_s;
  63. CoolBignum max_int_s;                // No constructor called
  64. CoolBignum max_long_s;                // for dynamic libraries,
  65. CoolBignum max_float_s;                // so these bignums are blank
  66. CoolBignum max_double_s;            
  67.  
  68. // Reinitialize one more time, if default constructor is called for 
  69. // above globals.
  70.  
  71. CoolBignum_Init bignum_init2_s;        // Offset static/dynamic difference
  72.  
  73. CoolBignum_Init::CoolBignum_Init() {
  74.   if ((count++ == 0) ||                // from bignum_init1_s
  75.       (double(max_double_s) == 0.0)) {        // from bignum_init2_s
  76.     data_bits_s   = BITS(Data);            // This initializer creates
  77.     radix_s       = long(pow(2,data_bits_s));    // correct values for
  78.     zero_s       = CoolBignum();        // above global objects,
  79.     one_s        = CoolBignum(long(1));        // as soon as Bignum.h is
  80.     eight_s      = CoolBignum(long(8));        // included as header in
  81.     ten_s        = CoolBignum(long(10));    // main.C
  82.     sixteen_s    = CoolBignum(long(16));
  83.     max_short_s  = CoolBignum(long(MAXSHORT));
  84.     max_int_s    = CoolBignum(long(MAXINT));
  85.     max_long_s   = CoolBignum(MAXLONG);
  86.     max_float_s  = CoolBignum(MAXFLOAT);
  87.     max_double_s = CoolBignum(MAXDOUBLE);
  88.   }
  89. }
  90.  
  91. CoolBignum_Init::~CoolBignum_Init() {}        // no clean up needed
  92.  
  93.  
  94.  
  95.  
  96.  
  97. // CoolBignum - simple constructor
  98. // Inputs:  none
  99. // Outputs:  initialized CoolBignum
  100.  
  101. CoolBignum::CoolBignum () {
  102.   this->data = NULL;                // No need to allocate yet
  103.   this->count = 0;                // Size of data is 0
  104.   this->sign = 1;                // CoolBignum >= 0
  105.   this->state = N_OK;                // State is ok
  106. }
  107.  
  108.  
  109.  
  110. // ~CoolBignum - destructor
  111. // Inputs:  none
  112. // Outputs:  none
  113.  
  114. CoolBignum::~CoolBignum () {
  115.   delete [] this->data;            // Delete any allocated data
  116. }
  117.  
  118.  
  119.  
  120. // CoolBignum - CoolBignum constructor with long argument
  121. // Inputs:  long to be converted to CoolBignum
  122. // Outputs:  new CoolBignum
  123.  
  124. CoolBignum::CoolBignum (const long inval) {
  125.   long l = inval;
  126.   if (l >= 0)                    // Get correct sign
  127.     this->sign = 1;
  128.   else {
  129.     l = -l;                    // Get absolute value of l
  130.     this->sign = -1;
  131.   }
  132.   Data buf[sizeof(l)];            // Temp buffer to store l in
  133.   Counter i = 0;            // buffer index
  134.   while (l) {                // While more bits in l
  135.     if (i >= sizeof(l)) {        // If no more buffer space
  136.       this->state = N_NO_CONVERSION;    //   raise an exception
  137.       no_conversion("CoolBignum(long)");
  138.     }
  139.     buf[i] = Data(l);                // Peel off lower order bits
  140.     l >>= data_bits_s;                // Shift next bits into place
  141.     i++;                
  142.   }
  143.   this->data = ((this->count = i) > 0 ?    // Allocate permanent data
  144.     new Data[i] : 0);
  145.   i = 0;                       
  146.   while (i < this->count) {            // Save buffer into perm. data
  147.     this->data[i] = buf[i];
  148.     i++;
  149.   }
  150.   this->state = N_OK;                // Set status to OK
  151. }
  152.  
  153.  
  154. // CoolBignum - CoolBignum constructor with double argument
  155. // Inputs:  double to be converted to CoolBignum
  156. // Outputs:  new CoolBignum
  157.  
  158. CoolBignum::CoolBignum (const double inval) {
  159.   double d = inval;
  160.   if (d >= 0)                    // Get sign of d
  161.     this->sign = 1;
  162.   else {
  163.     d = -d;                    // Get absolute value of d
  164.     this->sign = -1;
  165.   }
  166. #ifdef DBLRET_HACK   //## delete me after Borland fixes BC++ 3.1 bug
  167.   // need to assign 'double' return value to temporary because of small error
  168.   const double LOG10_MAXDOUBLE = log10(MAXDOUBLE);
  169.   const double LOG10_RADIX_S = log10(radix_s);
  170.   const int buf_size_s = int(LOG10_MAXDOUBLE/LOG10_RADIX_S);
  171.   if (buf_size_s==63 && d==MAXDOUBLE) {
  172.     printf("buf_size_s is 63 for MAXDOUBLE!\n");
  173.     cout << setprecision(16) << MAXDOUBLE << ' ' << radix_s << ' ' << LOG10_MAXDOUBLE << ' ' << LOG10_RADIX_S << ' ' << buf_size_s << endl;
  174.     abort();
  175.     }
  176. #else  // 
  177.   static int buf_size_s = 
  178.     int (log10(MAXDOUBLE)/log10(radix_s));    // Size of buffer to convert d
  179. #endif
  180.   Data *buf = new Data[buf_size_s];        // Buffer to convert d into
  181.   Counter i = 0;                    // buffer index
  182.     while (d >= 1.0) {                
  183.     if (i >= buf_size_s) {            // If no more buffer space
  184.       this->state = N_NO_CONVERSION;        //   raise an exception
  185.       no_conversion("CoolBignum(double)");
  186.     }
  187.     buf[i] = Data(fmod(d,radix_s));        // Get next data "digit" from d
  188.     d /= radix_s;                // Shift d right 1 data "digit"
  189.     i++;                    // Increment buffer index
  190.   }
  191.   this->data = (i > 0 ? new Data[i] : 0);    // Allocate permanent data
  192.   this->count = i;                // Save count
  193.   i = 0;                       
  194.   while (i < this->count) {            // Copy temp buffer into 
  195.     this->data[i] = buf[i];            //   permanent data
  196.     i++;
  197.   }
  198.   this->state = N_OK;                // Set status to OK
  199.   delete [] buf;                // Deallocate buffer
  200. }
  201.  
  202.  
  203.  
  204. // dtoBignum -- convert decimal string to CoolBignum
  205. // Inputs:  string representation of decimal literal to be converted
  206. // Outputs:  number of characters actually converted
  207.  
  208. int CoolBignum::dtoBignum (const char *s) {
  209.   Counter len = 0;                // No chars converted yet
  210.   if (s[0] == '-' || s[0] == '+') len++;    // Skip over leading +,-
  211.   while (isdigit(s[len])) {            // If current char is digit
  212.     (*this) = ((*this) * ten_s) +        // Shift CoolBignum left a decimal
  213.       CoolBignum(long(s[len++] - '0'));        //   digit and add new digit
  214.   }
  215.   if (s[0] == '-') this->sign = -1;        // If s had leading -, note it
  216.   return len;                    // Return # of chars processed
  217. }
  218.  
  219.  
  220.  
  221. // exptoBignum -- convert exponential string to a CoolBignum
  222. // Inputs:  string representation of exponential literal to be converted
  223. // Outputs:  none
  224.  
  225. void CoolBignum::exptoBignum (const char *s) {
  226.   Counter pos = this->dtoBignum(s) + 1;        // Convert the base, skip [eE]
  227.   long pow = atol(s + pos);            // Convert the exponent to long
  228.   while (pow-- > 0)                 // Raise CoolBignum to the given
  229.     *this = (*this) * ten_s;            //   power
  230. }
  231.  
  232.  
  233.  
  234. // ctox - convert hex character to integer hex value (ASCII or EBCDIC)
  235. // Inputs:  character representation of a hex number
  236. // Outputs:  integer value of the hex number
  237.  
  238. unsigned int ctox (int c) {
  239.   if ('0' <= c && c <= '9')
  240.     return c - '0';
  241.   if ('a' <= c && c <= 'f')
  242.     return c - 'a' + 10;
  243.   return c - 'A' + 10;
  244. }
  245.  
  246.  
  247.  
  248. // xtoBignum -- convert hex string to CoolBignum value
  249. // Inputs:  string representation of hex number to be converted
  250. // Outputs:  none
  251.  
  252. void CoolBignum::xtoBignum (const char *s) {
  253.   Counter size = strlen(s);
  254.   Counter len = 2;                // skip leading "0x"
  255.   while (len < size) {                // While there are more chars
  256.     (*this) = ((*this) * sixteen_s) +        // Shift CoolBignum left one hex
  257.       CoolBignum(long(ctox(s[len++])));        //   digit and add next digit
  258.   }
  259. }
  260.  
  261.  
  262.   
  263. // otoBignum -- convert octal string to CoolBignum
  264. // Inputs:  string representation of octal number to be converted
  265. // Outputs:  none
  266.  
  267. void CoolBignum::otoBignum (const char *s) {
  268.   Counter size = strlen(s);
  269.   Counter len = 0;                // No chars converted yet
  270.   while (len < size) {                // While there are more chars
  271.     (*this) = ((*this) * eight_s) +        // Shift CoolBignum left 1 oct dig.
  272.       CoolBignum(long(s[len++] - '0'));        // Add next character value
  273.   }
  274. }
  275.  
  276.  
  277.  
  278. // CoolBignum -- CoolBignum constructor with string argument
  279. // Inputs:  string representation of number to be converted to CoolBignum
  280. // Outputs:  new CoolBignum with converted value
  281.  
  282. CoolBignum::CoolBignum (const char *s) {
  283.   static CoolRegexp                    // Declare CoolRegexp's for
  284.     decimal("^[-+]?[1-9][0-9]*$"),              // decimal
  285.     exponential("^[-+]?[1-9][0-9]*[eE][1-9][0-9]*$"), // exponential
  286.     hexadecimal("^[0][xX][0-9a-fA-F]+$"),          // hex
  287.     octal("^[0][0-7]*$");                  // octal.
  288.  
  289.   // Init *this to a CoolBignum value of 0
  290.   this->data = 0;            
  291.   this->count = 0;                
  292.   this->sign = 1;                
  293.   this->state = N_OK;
  294.  
  295.   if (decimal.find(s))                // If string is decimal
  296.     this->dtoBignum(s);                // convert decimal to CoolBignum
  297.   else if (exponential.find(s))            // If string is exponential
  298.     this->exptoBignum(s);            // convert exp. to CoolBignum
  299.   else if (hexadecimal.find(s))            // If string is hex,
  300.     this->xtoBignum(s);                // convert hex to CoolBignum
  301.   else if (octal.find(s))            // If string is octal
  302.     this->otoBignum(s);                // convert octal to CoolBignum
  303.   else {                    // Otherwise
  304.     this->state = N_NO_CONVERSION;        // raise an exception
  305.     no_conversion("CoolBignum(const char *)");
  306.   }
  307. }
  308.  
  309.  
  310.  
  311. // CoolBignum - CoolBignum constructor with CoolBignum reference argument
  312. // Inputs:  reference to CoolBignum
  313. // Outputs:  new CoolBignum with same value as input
  314.  
  315. CoolBignum::CoolBignum (const CoolBignum& b) {
  316.   this->count = b.count;            // Copy b's count
  317.   this->data =                    // Allocate data if necessary
  318.     (b.count > 0 ? new Data[b.count] : 0);
  319.   for (Counter i = 0; i < this->count; i++)    // Copy b's data 
  320.     this->data[i] = b.data[i];    
  321.   this->sign = b.sign;                // Copy b's sign
  322.   this->state = b.state;            // Copy b's state
  323. }
  324.  
  325.  
  326.  
  327. // operator= -- overloaded CoolBignum assignment operator
  328. // Inputs:  reference to CoolBignum to be assigned
  329. // Outputs:  reference to modified CoolBignum
  330.  
  331. CoolBignum& CoolBignum::operator= (const CoolBignum& b) {
  332.   if (this != &b) {                // So long as b is not "this"
  333.     delete [] this->data;            // Delete existing data
  334.     this->count = b.count;            // Copy b's count
  335.     this->data =                // Allocate data if necessary
  336.       (this->count > 0 ? new Data[this->count] : 0);
  337.     for (Counter i = 0; i < this->count; i++)    // Copy b's data
  338.       this->data[i] = b.data[i];
  339.     this->sign = b.sign;            // Copy b's sign
  340.     this->state = b.state;            // Copy b's state
  341.   }
  342.   return *this;                    // Return reference 
  343. }
  344.  
  345.  
  346.  
  347. // operator- -- overloaded unary minus operator
  348. // Inputs:  none
  349. // Outputs:  CoolBignum, negated
  350.  
  351. CoolBignumE CoolBignum::operator- () const {
  352.   CoolBignum temp(*this);            // Temp stores result
  353.   if (temp.count)                // So long as this is non-zero
  354.     temp.sign *= -1;                // Flip its sign
  355.   CoolBignumE& result = *((CoolBignumE*) &temp);// same physical object
  356.   return result;                // shallow swap on return
  357. }
  358.  
  359.  
  360. // operator++ overloaded increment operator for CoolBignums
  361. // Inputs:  none
  362. // Outputs:  reference to this CoolBignum, incremented
  363.  
  364. CoolBignum& CoolBignum::operator++ () {
  365.   static CoolBignum one_s = 1l;            // static CoolBignum equal to 1
  366.   *this = *this + one_s;;            // add one to this CoolBignum
  367.   return *this;                    // return reference to this B.
  368. }
  369.  
  370.  
  371.  
  372. // operator--  overloaded decrement operator for CoolBignums
  373. // Inputs:  none
  374. // Outputs:  this CoolBignum, decremented
  375.  
  376. CoolBignum& CoolBignum::operator-- () {
  377.   static CoolBignum one_s = 1l;            // static CoolBignum equal to 1
  378.   *this = *this - one_s;            // add one to this CoolBignum
  379.   return *this;                    // return reference to this B.
  380. }
  381.  
  382.  
  383.  
  384. // resize -- change the data allotment for a CoolBignum
  385. // Inputs:  new size of data allotment
  386. // Outputs:  none
  387.  
  388. void CoolBignum::resize (Counter new_count) {
  389.   if (new_count != this->count) {        // If new size is really new
  390.     Data *new_data =                // Allocate data if necessary
  391.       (new_count > 0 ? new Data[new_count] : 0);
  392.  
  393.     if (this->count <= new_count) {        // Copy old data into new
  394.       for (Counter i = 0; i < this->count; i++)  
  395.         new_data[i] = this->data[i];
  396.       for (; i < new_count; i++)
  397.         new_data[i] = 0;
  398.     }
  399.     else {                       
  400.       for (Counter i = 0; i < new_count; i++)  
  401.         new_data[i] = this->data[i];
  402.     }
  403.  
  404.     delete [] this->data;            // Get rid of old data
  405.     this->data = new_data;            // Point to new data
  406.     this->count = new_count;            // Save new count
  407.   }
  408. }
  409.  
  410.  
  411.  
  412. // trim -- trim CoolBignum of excess data allotment
  413. // Inputs:  none
  414. // Outputs:  reference to modified CoolBignum
  415.  
  416. CoolBignum& CoolBignum::trim () {
  417.   for (Counter i = this->count; i > 0; i--)    // Skip over high-order words
  418.     if (this->data[i - 1] != 0) break;        //   that are zero
  419.   if (i < this->count) {            // If there are some such words
  420.     Counter oldcount = this->count;
  421.     this->count = i;                // Update the count
  422.     Data *new_data = (i > 0 ? new Data[i] : 0);    // Allocate data if necessary
  423.     for (; i > 0; i--)                // Copy old data into new
  424.       new_data[i - 1] = this->data[i - 1];
  425.     delete [] this->data;            // Delete old data
  426.     this->data = new_data;            // Point to new data
  427.   }
  428.   return *this;                    // return reference to CoolBignum
  429. }
  430.  
  431.  
  432. // add -- add two CoolBignum values and save their sum
  433. // Inputs:  references to two CoolBignum addends and the resulting sum
  434. // Outputs:  none
  435.  
  436. void add (const CoolBignum& b1, const CoolBignum& b2, CoolBignum& sum) {
  437.   const CoolBignum *bmax, *bmin;            // Determine which of the two
  438.   if (b1.count >= b2.count) {            //   addends has the most
  439.     bmax = &b1;                    //   data.
  440.     bmin = &b2;
  441.   }
  442.   else {
  443.     bmax = &b2;
  444.     bmin = &b1;
  445.   }
  446.   sum.data = ((sum.count = bmax->count) > 0 ?    // Allocate data for their sum
  447.           new Data[sum.count] : 0);
  448.   unsigned long temp, carry = 0;
  449.   Counter i = 0;
  450.   while (i < bmin->count) {            // Add, element by element.
  451.     // Add both elements and carry
  452.     temp = (unsigned long)b1.data[i] + (unsigned long)b2.data[i] + carry;
  453.     carry = temp/radix_s;            // keep track of the carry
  454.     sum.data[i] = Data(temp);            // store sum
  455.     i++;                    // go to next element
  456.   }
  457.   while (i < bmax->count) {            // bmin has no more elements
  458.     temp = bmax->data[i] + carry;        // propagate the carry through
  459.     carry = temp/radix_s;            // the rest of bmax's elements
  460.     sum.data[i] = Data(temp);            // store sum
  461.     i++;
  462.   }
  463.   if (carry) {                    // if carry left over
  464.     sum.resize(bmax->count + 1);        //   allocate another word
  465.     sum.data[bmax->count] = 1;            //   save the carry in it
  466.   }
  467. }
  468.  
  469.  
  470.  
  471. // subtract - subtract min CoolBignum from max CoolBignum (unsigned), result in diff
  472. // Inputs:  references to CoolBignum
  473. // Outputs:  none
  474.  
  475. void subtract (const CoolBignum& bmax, const CoolBignum& bmin, CoolBignum& diff) {
  476.   diff.data = new Data[diff.count = bmax.count];// Allocate data for difference
  477.   unsigned long temp;
  478.   int borrow = 0;
  479.   for (Counter i = 0; i < bmin.count; i++) {    // Subtract word by word.
  480.     
  481.     temp = (unsigned long)bmax.data[i] 
  482.       + (unsigned long)radix_s - borrow;    // Add radix to bmax's data
  483.     temp -= (unsigned long)bmin.data[i];    // Subtract off bmin's data
  484.     borrow = (temp/radix_s == 0);        // Did we have to borrow?
  485.     diff.data[i] = (Data) temp;            // Reduce modulo radix and save
  486.   }
  487.   for (; i < bmax.count; i++) {            // No more data for bmin
  488.     temp = (unsigned long)bmax.data[i] 
  489.       + (unsigned long)radix_s - borrow;    // Propagate the borrow through
  490.     borrow = (temp/radix_s == 0);        //   rest of bmax's data
  491.     diff.data[i] = (Data) temp;
  492.   }
  493.   diff.trim();                    // Done. Now trim excess data
  494. }
  495.  
  496.  
  497.  
  498. // magnitude_cmp - compare absolute values of two CoolBignums
  499. // Inputs:  two CoolBignums
  500. // Outputs:  result of comparison:  -1 if abs(b1) < abs(b2)
  501. //                                   0 if abs(b1) == abs(b2)
  502. //                                  +1 if abs(b1) > abs(b2)
  503.  
  504. int magnitude_cmp (const CoolBignum& b1, const CoolBignum& b2) {
  505.   if (b1.count > b2.count) return 1;        // If one has more data than
  506.   if (b2.count > b1.count) return -1;        //   the other, it wins
  507.   Counter i = b1.count;                // Else same number of elmts
  508.   while (i > 0) {                // Do lexicographic comparison
  509.     if (b1.data[i - 1] > b2.data[i - 1])    
  510.       return 1;                    
  511.     else if (b1.data[i - 1] < b2.data[i - 1])    
  512.       return -1;
  513.     i--;
  514.   }                        // No data, or all elmts same
  515.   return 0;                    //  so must be equal
  516. }
  517.  
  518.  
  519.  
  520. // operator+ -- overloaded CoolBignum addition operator
  521. // Inputs:  two references to CoolBignum addends
  522. // Outputs:  new CoolBignum sum
  523.  
  524. CoolBignumE operator+ (const CoolBignum& b1, const CoolBignum& b2) {
  525.   CoolBignum sum;                // Init sum to zero
  526.   if (b1.sign == b2.sign) {            // If both have same sign
  527.     add(b1,b2,sum);                //   Do simple addition
  528.     sum.sign = b1.sign;                // Attach proper sign
  529.   }
  530.   else {                    // Else different signs
  531.     int mag = magnitude_cmp(b1,b2);        // Determine relative sizes
  532.     if (mag > 0) {                // If abs(b1) > abs(b2)
  533.       subtract(b1,b2,sum);            //   sum = b1 - b2
  534.       sum.sign = b1.sign;            // Sign of sum follows b1
  535.     }
  536.     else if (mag < 0) {                // Else if abs(b1) < abs(b2)
  537.       subtract(b2,b1,sum);            //   sum = b2 - b1
  538.       sum.sign = b2.sign;            // Sign of sum follows b2
  539.     }                        // (Else abs(b1) == abs(b2)
  540.   }                        //   so sum must be zero)
  541.   CoolBignumE& result = *((CoolBignumE*) &sum);    // same physical object
  542.   return result;                // shallow swap on return
  543. }
  544.  
  545.  
  546. // multiply_aux -- multiply a CoolBignum by a "single digit"
  547. // Inputs:  CoolBignum reference, single word multiplier, reference to the product,
  548. //          and index of starting storage location to use in product
  549. // Outputs:  none
  550.  
  551. void multiply_aux (const CoolBignum& b, Data d, CoolBignum& prod, Counter i) {
  552.   // this function works just like normal multiplication by hand, in that the
  553.   // top number is multiplied by the first digit of the bottom number, then the
  554.   // second digit, and so on.  The only difference is that instead of doing all
  555.   // of the multiplication before adding the rows, addition is done
  556.   // concurrently.
  557.   Counter j;
  558.   if (i == 0) {                    // if index is zero
  559.     j = 0;                    //   then zero out all of
  560.     while (j < prod.count)            //   prod's data elements
  561.       prod.data[j++] = 0;           
  562.   }
  563.   if (d != 0) {                    // if d == 0, nothing to do
  564.     unsigned long temp;
  565.     Data carry = 0;
  566.  
  567.     for (Counter j = 0; j < b.count; j++) {    
  568.       // for each of b's data elmts, multiply times d and add running product
  569.       temp = (unsigned long)b.data[j] * (unsigned long)d
  570.     + (unsigned long)prod.data[i + j] + carry;
  571.       prod.data[i + j] = Data(temp % radix_s);    //   store result in product
  572.       carry = Data(temp/radix_s);        //   keep track of carry
  573.     }
  574.     if (i+j < prod.count)
  575.       prod.data[i + j] = carry;            // Done.  Store the final carry
  576.   }
  577. }
  578.  
  579.  
  580.  
  581. // operator* -- overload * for CoolBignums
  582. // Inputs:  references to two CoolBignum multiplicands
  583. // Outputs:  CoolBignum product
  584.  
  585. CoolBignumE operator* (const CoolBignum& b1, const CoolBignum& b2) {
  586.   CoolBignum prod;                //   init product to zero
  587.   if (b1 != zero_s && b2 != zero_s) {        // if neither multiplicand == 0
  588.     prod.data =                    //   allocate data for product
  589.       new Data[prod.count = b1.count + b2.count];
  590.     for (Counter i = 0; i < b2.count; i++)    //   multiply each b2 "digit" 
  591.       multiply_aux(b1, b2.data[i], prod, i);    //   times b1 and add to total
  592.     prod.sign = b1.sign * b2.sign;        //   determine correct sign
  593.     prod.trim();                //   trim excess data and ret.
  594.   }
  595.   CoolBignumE& result = *((CoolBignumE*) &prod);// same physical object
  596.   return result;                // shallow swap on return
  597. }
  598.  
  599.  
  600.  
  601. // normalize -- normalize two CoolBignums  (Refer to Knuth, V.2, Section 4.3.1,
  602. //              Algorithm D for details.  A digit here is one data element in
  603. //              the radix 2**sizeof(Data).)
  604. // Inputs:  references to two CoolBignums b1, b2, and their normalized counterparts
  605. // Outputs:  the integral normalization factor used
  606.  
  607. Data normalize (const CoolBignum& b1, const CoolBignum& b2, CoolBignum& u, CoolBignum& v) {
  608.   Data d =                    // Calcualte normalization
  609.     Data(radix_s/(long(b2.data[b2.count - 1]) + 1));    //   factor.
  610.                 //^^^^- JAM added this cast because Test#115 was overflowing resulting
  611.                 // in Divide Error because value was 65535 and wrapping to 0 with +1
  612.   u.data = new Data[u.count = b1.count + 1];    // Get data for u (plus extra)
  613.   v.data = new Data[v.count = b2.count];    // Get data for v
  614.   u.data[b1.count] = 0;                // Set u's leading digit to 0
  615.   multiply_aux(b1,d,u,0);            // u = b1 * d
  616.   multiply_aux(b2,d,v,0);            // v = b2 * d
  617.   return d;                    // return normalization factor
  618. }
  619.  
  620.  
  621.  
  622. // divide_aux -- divide a CoolBignum by a "single digit" (Refer to Knuth, V.2,
  623. //               Section 4.3.2, exercise 16 for details.  A digit here is one
  624. //               data element in the radix 2**sizeof(Data).)
  625. // Inputs:  reference to CoolBignum dividend, single digit divisor d, CoolBignum
  626. //          quotient, and single digit remainder r
  627. // Outputs:  none
  628.  
  629. void divide_aux (const CoolBignum& b1, Data d, CoolBignum& q, Data& r) {
  630.   r = 0;                    // init remainder to zero
  631.   unsigned long temp;
  632.   for (Counter j = b1.count; j > 0; j--) {
  633.     temp = (unsigned long)r*radix_s 
  634.       + (unsigned long)b1.data[j - 1];        // get remainder, append next
  635.     if (j-1 < q.count) 
  636.       q.data[j - 1] = Data(temp/d);        //   digit, then divide
  637.     r = Data(temp % d);                // calculate new remainder
  638.   }
  639. }
  640.  
  641.  
  642. // estimate_q_hat -- estimate next dividend (Refer to Knuth, V.2, Section
  643. //                   4.3.1, Algorithm D for details.  This function estimates
  644. //                   how many times v goes into u, starting at u's jth digit.
  645. //                   A digit here is actually a data element, thought of as
  646. //                   being in the radix 2**sizeof(Data).)
  647. // Inputs:  reference to CoolBignum dividend and divisor and starting digit j
  648. // Outputs:  estimated number of times v goes into u
  649.  
  650. Data estimate_q_hat (const CoolBignum& u, const CoolBignum& v, Counter j) {
  651.   Data q_hat,
  652.        v1 = v.data[v.count - 1],        // localize frequent data
  653.        v2 = v.data[v.count - 2],
  654.        u0 = u.data[u.count - 1 - j],
  655.        u1 = u.data[u.count - 2 - j],
  656.        u2 = u.data[u.count - 3 - j];
  657.  
  658.   // Initial Knuth estimate, usually correct
  659.   q_hat = Data(u0 == v1 ?            
  660.            radix_s - 1 :            
  661.            (u0*radix_s + u1)/v1);
  662.  
  663.   // high speed test to determine most of the cases in which initial
  664.   // estimate is too large.  Eliminates most cases in which q_hat is one too
  665.   // large.  Eliminates all cases in which q_hat is two too large.  The test
  666.   // looks hairy because we have to watch out for overflow.  In the book, this
  667.   // test is the simple inequality:
  668.   //     v2*q_hat > (u0*radix_s + u1 - q_hat*v1)*radix_s + u2.
  669.   // If the inequality is true, decrease q_hat by 1.  If inequality is still
  670.   // true, decrease q_hat again.
  671.   unsigned long lhs, rhs;        // lhs, rhs of Knuth inequality
  672.   for (Counter i = 0; i < 2; i++) {    // loop at most twice
  673.     lhs = v2 * q_hat;            // Calculate left-hand side of ineq.
  674.     rhs = u0 * radix_s + u1;        // Calculate part of right-hand side 
  675.     rhs -= (q_hat * v1);        // Now subtract off part
  676.     
  677.     // DML:  My attempt to fix the overflow testing bug..
  678.     double temp_rhs = double(rhs);
  679.     double temp_radix_s = double(radix_s);
  680.     // OLD WAY: if (rhs > rhs * radix_s)// if multiplication causes overflow
  681.     // NEW WAY: see if result won't fit into a long.
  682.     if ( temp_rhs * temp_radix_s > double(MAXLONG) )
  683.       break;                //   then rhs > lhs, so test fails
  684.     rhs *= radix_s;            // No overflow:  ok to multiply
  685.  
  686.     temp_rhs = double(rhs);
  687.     double temp_u2 = double(u2);
  688.     // OLD WAY: if (rhs > rhs + u2)    // if addition yields overflow
  689.     if ( temp_rhs + temp_u2 > double(MAXLONG) ) // NEW WAY.
  690.       break;                //   then rhs > lhs, so test fails
  691.     rhs += u2;                // No overflow: ok to add.
  692.     if (lhs <= rhs)            // if lhs <= rhs
  693.       break;                //   test fails
  694.     q_hat--;                // Test passes:  decrement q_hat
  695.   }                    // Loop again
  696.   return q_hat;                // Return estimate
  697. }
  698.  
  699. // Original version.
  700. // Data estimate_q_hat (const CoolBignum& u, const CoolBignum& v, Counter j) {
  701. //   Data q_hat,
  702. //        v1 = v.data[v.count - 1],        // localize frequent data
  703. //        v2 = v.data[v.count - 2],
  704. //        u0 = u.data[u.count - 1 - j],
  705. //        u1 = u.data[u.count - 2 - j],
  706. //        u2 = u.data[u.count - 3 - j];
  707. // 
  708. //   // Initial Knuth estimate, usually correct
  709. //   q_hat = Data(u0 == v1 ?            
  710. //            radix_s - 1 :            
  711. //            (u0*radix_s + u1)/v1);
  712. // 
  713. //   // high speed test to determine most of the cases in which initial
  714. //   // estimate is too large.  Eliminates most cases in which q_hat is one too
  715. //   // large.  Eliminates all cases in which q_hat is two too large.  The test
  716. //   // looks hairy because we have to watch out for overflow.  In the book, this
  717. //   // test is the simple inequality:
  718. //   //     v2*q_hat > (u0*radix_s + u1 - q_hat*v1)*radix_s + u2.
  719. //   // If the inequality is true, decrease q_hat by 1.  If inequality is still
  720. //   // true, decrease q_hat again.
  721. //   unsigned long lhs, rhs;        // lhs, rhs of Knuth inequality
  722. //   for (Counter i = 0; i < 2; i++) {    // loop at most twice
  723. //     lhs = v2 * q_hat;            // Calculate left-hand side of ineq.
  724. //     rhs = u0 * radix_s + u1;        // Calculate part of right-hand side 
  725. //     rhs -= (q_hat * v1);        // Now subtract off part
  726. //     if (rhs > rhs * radix_s)        // if multiplication causes overflow
  727. //       break;                //   then rhs > lhs, so test fails
  728. //     rhs *= radix_s;            // No overflow:  ok to multiply
  729. //     if (rhs > rhs + u2)            // if addition yields overflow
  730. //       break;                //   then rhs > lhs, so test fails
  731. //     rhs += u2;                // No overflow: ok to add.
  732. //     if (lhs <= rhs)            // if lhs <= rhs
  733. //       break;                //   test fails
  734. //     q_hat--;                // Test passes:  decrement q_hat
  735. //   }                    // Loop again
  736. //   return q_hat;                // Return estimate
  737. // }
  738.  
  739.  
  740.  
  741. // multiply_subtract -- calculate u - v*q_hat (Refer to Knuth, V. 2, Section
  742. //                      4.3.1, Algorithm D for details.  A digit here is a
  743. //                      data element, thought of as being in the radix
  744. //                      2**sizeof(Data).)
  745. // Inputs:  reference to CoolBignum dividend, divisor, estimated result, and index
  746. //          into jth digit of dividend
  747. // Outputs:  true number of times v goes into u
  748.  
  749. Data multiply_subtract (CoolBignum& u, const CoolBignum& v, Data q_hat, Counter j) {
  750.   // At this point it has been estimated that v goes into the jth and higher
  751.   // digits of u about q_hat times, and in fact that q_hat is either the
  752.   // correct number of times or one too large.
  753.  
  754.   if (q_hat == 0) return q_hat;                    // if q_hat 0, nothing to do
  755.   CoolBignum rslt;                    // create a temporary CoolBignum
  756.   Counter tmpcnt;
  757.   rslt.data =                    // allocate data for it
  758.      new Data[rslt.count = v.count + 1];
  759.  
  760.   // simultaneous computation of u - v*q_hat
  761.   unsigned long prod, diff;
  762.   Data carry = 0, borrow = 0;
  763.   for (Counter i = 0; i < v.count; i++) {    
  764.     // for each digit of v, multiply it by q_hat and subtract the result
  765.     prod = (unsigned long)v.data[i] * (unsigned long)q_hat + carry;
  766.     diff = (unsigned long)u.data[u.count - v.count - 1 - j + i]
  767.            + (unsigned long)radix_s - borrow;
  768.     diff -= (unsigned long)Data(prod);        //   form proper digit of u
  769.     rslt.data[i] = Data(diff);            //   save the result
  770.     borrow = (diff/radix_s == 0);        //   keep track of any borrows
  771.     carry = Data(prod/radix_s);            //   keep track of carries
  772.   }
  773.   tmpcnt = u.count - v.count - 1 - j + i;
  774.   diff = (unsigned long)u.data[tmpcnt]        //  special case for the last
  775.          + (unsigned long)radix_s - borrow;    //     digit
  776.   diff -= carry;
  777.   rslt.data[i] = Data(diff);
  778.   borrow = (diff/radix_s == 0);
  779.  
  780.   // A leftover borrow indicates that u - v*q_hat is negative, i.e., that
  781.   // q_hat was one too large.  So to get correct result, decrement q_hat and
  782.   // add back one multiple of v
  783.   if (borrow) {
  784.     q_hat--;
  785.     carry = 0;
  786.     unsigned long sum;
  787.     for (i = 0; i < v.count; i++) {
  788.       sum = (unsigned long)rslt.data[i] + (unsigned long)v.data[i] + carry;
  789.       carry = Data(sum/radix_s);
  790.       u.data[u.count - v.count - 1 - j + i] = Data(sum);
  791.     }
  792.     u.data[u.count - v.count - 1 - j + i] = rslt.data[i] + carry;
  793.   }
  794.   else {                    // otherwise, result is ok
  795.     for (i = 0; i < rslt.count; i++)        // store result back into u
  796.       u.data[u.count - v.count - 1 - j + i] = 
  797.     rslt.data[i];
  798.   }
  799.   return q_hat;                    // return corrected q_hat
  800. }
  801.  
  802.  
  803.  
  804. // divide - divide b2 into b1, getting quotient q and remainder r.  (Refer to
  805. //          Knuth, V.2, Seciton 4.3.1, Algorithm D for details.  This function
  806. //          implements Algorithm D.)
  807. // Inputs:  references to a CoolBignum dividend b1, divisor b2, quotient q, and
  808. //          remainder r.
  809. // Outputs:  none
  810.  
  811. void divide (const CoolBignum& b1, const CoolBignum& b2, CoolBignum& q, CoolBignum& r) {
  812.   q = r = zero_s;
  813.   if (b1 == zero_s)             // If divisor is zero
  814.     return;                 //   return zero quotient and remainder
  815.   int mag = magnitude_cmp(b1,b2);    // Compare magnitudes
  816.   if (mag < 0)                 // if abs(b1) < abs(b2)
  817.     r = b1;                 //   return zero quotient, b1 remainder
  818.   else if (mag == 0)             // if abs(b1) == abs(b2)
  819.     q = one_s;                 //   quotient is 1, remainder is 0
  820.   else {                 // otherwise abs(b1) > abs(b2), so divide
  821.     q.data = new Data[q.count = b1.count - b2.count + 1]; // Allocate quotient
  822.     r.data = new Data[r.count = b2.count];          // Allocate remainder
  823.     if (b2.count == 1) {            // Single digit divisor?
  824.       divide_aux(b1,b2.data[0],q,r.data[0]);    // Do single digit divide
  825.     }
  826.     else {                    // Else full-blown divide
  827.       CoolBignum u,v;
  828.       Data d = normalize(b1,b2,u,v);        // Set u = b1/d, v = b2/d
  829.       Data q_hat;                // Multiplier
  830.       Counter j = 0;
  831.       while (j <= b1.count - b2.count) {    // Main division loop
  832.         q_hat =    estimate_q_hat(u,v,j);        // Estimate # times v divides
  833.         q.data[q.count - 1 - j] =        // Do division, get true answ.
  834.       multiply_subtract(u,v,q_hat,j);
  835.     j++;
  836.       }
  837.       static Data dufus;            // dummy variable
  838.       divide_aux(u,d,r,dufus);            // Unnormalize u for remainder
  839.     }
  840.     q.trim();                    // Trim leading zeros of quot.
  841.     r.trim();                    // Trim leading zeros of rem.
  842.   }
  843.   q.sign = r.sign = b1.sign * b2.sign;        // Calculate signs
  844. }
  845.  
  846.  
  847.  
  848. // operator/ -- overload division operator for CoolBignums
  849. // Inputs:  references to CoolBignum numerator and denominator
  850. // Outputs:  CoolBignum quotient
  851.  
  852. CoolBignumE operator/ (const CoolBignum& b1, const CoolBignum& b2) {
  853.   CoolBignum q,r;                // Quotient and remainder
  854.   if (b2.count == 0) {                // If b2 is zero
  855.     if (b1.count == 0) {            // If b1 == zero
  856.       q.state = N_DIVIDE_BY_ZERO;        // Both num & den are zero
  857.       b1.divide_by_zero("operator/ ()");    // Raise the exception
  858.     }
  859.     else if (b1.sign > 0) {            // If b1 > zero
  860.       q.state = N_PLUS_INFINITY;        // Positive infinity
  861.       b1.plus_infinity("operator/ ()");        // Raise the exception
  862.     }
  863.     else if (b1.sign < 0) {            // If b1 < zero
  864.       q.state = N_MINUS_INFINITY;        // Negative infinity
  865.       b1.minus_infinity("operator/ ()");    // Raise the exception
  866.     }
  867.   }
  868.   else {
  869.     divide(b1,b2,q,r);                // Call divide fn
  870.   }
  871.   CoolBignumE& result = *((CoolBignumE*) &q);    // same physical object
  872.   return result;                // shallow swap on return
  873. }
  874.  
  875.  
  876.  
  877. // operator% -- overload modulus operator for CoolBignums
  878. // Inputs:  references to CoolBignum number and modulus
  879. // Outputs:  CoolBignum modulus result
  880.  
  881. CoolBignumE operator% (const CoolBignum& b1, const CoolBignum& b2) {
  882.   CoolBignum q,r;                  // Temporary quotient and remainder
  883.   if (b2.count == 0) {              // if b2 == 0
  884.     r.state = N_DIVIDE_BY_ZERO;          //   implies division by zero
  885.     b2.divide_by_zero("operator% ()"); //  raise an exception
  886.   }
  887.   else {                  // otherwise,
  888.     divide(b1,b2,q,r);              //   divide b1 by b2 and save remainder
  889.   }                     
  890.   CoolBignumE& result = *((CoolBignumE*) &r);    // same physical object
  891.   return result;                // shallow swap on return
  892. }
  893.  
  894.  
  895.  
  896. // left_shift -- left shift (arithmetic) CoolBignum by positive number.  
  897. // Inputs:  reference to CoolBignum, positive shift value
  898. // Outputs:  CoolBignum, multiplied by the corresponding power of two
  899.  
  900. CoolBignumE left_shift (const CoolBignum& b1, long l) {
  901.   // to carry out this arithmetic left shift, we cheat.  Instead of physically
  902.   // shifting the data array l bits to the left, we shift just enough to get
  903.   // the correct word alignment, and then pad the array on the right with as
  904.   // many zeros as we need.
  905.   CoolBignum rslt;                    // result of shift
  906.   rslt.sign = b1.sign;                // result follows sign of input
  907.   Counter growth = Counter(l / data_bits_s);    // # of words rslt will grow by
  908.   Data shift = Data(l % data_bits_s);        // amount to actually shift
  909.   Data rshift = data_bits_s - shift;        // amount to shift next word by
  910.   Data carry =                    // value that will be shifted
  911.     b1.data[b1.count - 1] >> (data_bits_s - shift); // out end of current array
  912.   rslt.data =                        // allocate new data array
  913.     new Data[rslt.count = b1.count + growth + (carry != 0 ? 1 : 0)];
  914.   Counter i = 0;                
  915.   while (i < growth)                // zero out padded elements
  916.     rslt.data[i++] = 0;
  917.   rslt.data[i++] = b1.data[0] << shift;        // shift first non-zero element
  918.   while (i < rslt.count - 1) {            // for remaining data words
  919.     rslt.data[i] = (b1.data[i - growth] << shift) + // shift current data word
  920.       (b1.data[i - 1 - growth] >> rshift);        // propagate adjacent
  921.     i++;                    // carry into current word
  922.   }
  923.   if (i < rslt.count) {
  924.     if (carry)                    // if last word had overflow
  925.       rslt.data[i] = carry;            //   store it new data
  926.     else                        // otherwise,
  927.       rslt.data[i] = (b1.data[i - growth] << shift) +    // do like the rest
  928.     (b1.data[i - 1 - growth] >> rshift);
  929.   }
  930.   CoolBignumE& result = *((CoolBignumE*) &rslt);// same physical object
  931.   return result;                // shallow swap on return
  932. }
  933.  
  934.  
  935.  
  936. // right_shift -- right shift (arithmetic) CoolBignum by positive number.  
  937. // Inputs:  reference to CoolBignum, positive shift value
  938. // Outputs:  CoolBignum, divided by the corresponding power of two
  939.  
  940. CoolBignumE right_shift (const CoolBignum& b1, long l) {
  941.   CoolBignum rslt;                    // result of shift
  942.   Counter shrinkage = Counter(l / data_bits_s);    // # of words rslt will shrink
  943.   Data shift = Data(l % data_bits_s);        // amount to actually shift
  944.   Data dregs = (b1.data[b1.count - 1] >> shift); // high end data to save
  945.   if (shrinkage + (dregs == 0) < b1.count) {    // if not all data shifted out
  946.     rslt.sign = b1.sign;            //   rslt follows sign of input
  947.                         //   allocate new data
  948.     rslt.data = new Data[rslt.count = b1.count - shrinkage
  949.          - (dregs == 0 ? 1 : 0)];
  950.     Data lshift = data_bits_s - shift;        //   amount to shift high word
  951.     Counter i = 0;
  952.     while (i < rslt.count - 1) {        //   shift current word
  953.       rslt.data[i] = (b1.data[i + shrinkage] >> shift) + // propagate adjacent
  954.         (b1.data[i + shrinkage + 1] << lshift);    //   word into current word
  955.       i++;
  956.     }
  957.     if (dregs)                    // don't lose dregs
  958.       rslt.data[i] = dregs;
  959.     else {
  960.       rslt.data[i] = (b1.data[i + shrinkage] >> shift) +
  961.         (b1.data[i + shrinkage + 1] << lshift);
  962.     }
  963.   }
  964.   CoolBignumE& result = *((CoolBignumE*) &rslt);// same physical object
  965.   return result;                // shallow swap on return
  966. }
  967.  
  968.  
  969. // operator<< -- overload left shift operator for CoolBignums
  970. // Inputs:  reference to CoolBignum to be shifted, left shift amount
  971. // Outputs:  shifted CoolBignum
  972.  
  973. CoolBignumE operator<< (const CoolBignum& b1, long l) {
  974.   if (l == 0 || b1 == zero_s) {            // if either arg is zero
  975.     CoolBignum b(b1);                // copy b1
  976.     CoolBignumE& result = *((CoolBignumE*) &b);    // same physical object
  977.     return result;                // shallow swap on return
  978.   }
  979.   if (l < 0)                    // if shift amt is negative
  980.     return right_shift(b1,-l);            //   do an actual right shift
  981.   else                        // otherwise
  982.     return left_shift(b1,l);            //   do a left shift
  983. }
  984.  
  985.  
  986. // operator>> -- overload right shift operator for CoolBignums
  987. // Inputs:  reference to CoolBignum to be shifted, right shift amount
  988. // Outputs:  shifted CoolBignum
  989.  
  990. CoolBignumE operator>> (const CoolBignum& b1, long l) {
  991.   if (l == 0 || b1 == zero_s) {            // if either arg is zero
  992.     CoolBignum b(b1);                // copy b1
  993.     CoolBignumE& result = *((CoolBignumE*) &b);    // same physical object
  994.     return result;                // shallow swap on return
  995.   }
  996.   if (l < 0)                    // if shift amt is negative
  997.     return left_shift(b1,-l);            //   do an actual left shift
  998.   else                        // else
  999.     return right_shift(b1,l);            //   do a right shift
  1000. }
  1001.  
  1002.  
  1003.  
  1004. // operator== -- overload equality operator for CoolBignums
  1005. // Inputs:  reference to CoolBignum to compare to
  1006. // Outputs:  Boolean equality indicator
  1007.  
  1008. Boolean CoolBignum::operator== (const CoolBignum& b) const {
  1009.   if (this->sign != b.sign) return FALSE;    // Different sign implies !=
  1010.   if (this->count != b.count) return FALSE;    // Different size implies !=
  1011.   for (Counter i = 0; i < this->count; i++)    // Each data element the same?
  1012.     if (this->data[i] != b.data[i]) return FALSE; // No. Return !=
  1013.   return TRUE;                      // Yes. Return ==
  1014. }
  1015.  
  1016.  
  1017.  
  1018. // operator< -- overload less-than operator for CoolBignums
  1019. // Inputs:  reference to CoolBignum to compare to
  1020. // Outputs:  Boolean less-than indicator
  1021.  
  1022. Boolean CoolBignum::operator< (const CoolBignum& b) const {
  1023.   if (this->sign < b.sign) return TRUE;        // Different signs?
  1024.   if (this->sign > b.sign) return FALSE;
  1025.   if (this->sign == 1)                // Both signs == 1
  1026.     return (magnitude_cmp(*this,b) < 0 ? TRUE: FALSE); // this must be smaller
  1027.   else                        // Both signs == -1
  1028.     return (magnitude_cmp(*this,b) > 0 ? TRUE: FALSE); // this must be larger
  1029. }
  1030.  
  1031.  
  1032.  
  1033. // operator> -- overload greater-than operator for CoolBignums
  1034. // Inputs:  reference to CoolBignum to compare to
  1035. // Outputs:  Boolean greater-than indicator
  1036.  
  1037. Boolean CoolBignum::operator> (const CoolBignum& b) const {
  1038.   if (this->sign > b.sign) return TRUE;        // Different signs?
  1039.   if (this->sign < b.sign) return FALSE;
  1040.   if (this->sign == 1)                // Both signs == 1
  1041.     return (magnitude_cmp(*this,b) > 0 ? TRUE: FALSE); // this must be larger
  1042.   else                        // Both signs == -1
  1043.     return (magnitude_cmp(*this,b) < 0 ? TRUE: FALSE); // this must be smaller
  1044. }
  1045.  
  1046.  
  1047.  
  1048. // operator<< -- overload output operator for CoolBignums
  1049. // Inputs:  reference to output stream and CoolBignum
  1050. // Outputs:  reference to output stream
  1051.  
  1052. ostream& operator<< (ostream& os, const CoolBignum& b) {
  1053.   CoolBignum d = b;                    // Copy the input CoolBignum
  1054.   if (d.sign == -1) {                // If it's negative
  1055.     cout.put('-');                //   Output leading minus sign
  1056.     d.sign = 1;                    //   Make d positive for divide
  1057.   }
  1058.   CoolBignum q,r;                    // Temp quotient and remainder
  1059.   char *cbuf = new char[5 * b.count];        // Temp character buffer
  1060.   Counter i = 0;
  1061.   do {                        // repeat:
  1062.     divide(d,ten_s,q,r);            //   Divide CoolBignum by ten
  1063.     cbuf[i++] = char(long(r) + '0');        //   Get one's digit
  1064.     d = q;                    //   Then discard one's digit
  1065.     q = r = zero_s;                //   Prep for next divide
  1066.   } while (d != zero_s);            // until no more one's digits
  1067.   do {                        // repeat;
  1068.     os.put(cbuf[--i]);                //   output char buf in reverse
  1069.   } while (i);                    // until no more chars
  1070.   delete [] cbuf;                // delete temp char buf
  1071.   return os;                    // return output stream
  1072. }
  1073.  
  1074.  
  1075.  
  1076. // operator short - conversion operator from CoolBignum to short
  1077. // Inputs:  none
  1078. // Outputs:  CoolBignum converted to short
  1079.  
  1080. CoolBignum::operator short () const {
  1081.   if (*this > max_short_s) {            // If short overflow
  1082.     overflow("operator short ()");        //   raise exception
  1083.   }
  1084.   if (*this < -max_short_s) {            // If short underflow
  1085.     underflow("operator short ()");        //   raise exception
  1086.   }
  1087.   short s = 0;                    // Default is zero conversion
  1088.   for (Counter i = this->count; i > 0; i--)
  1089.     s = short(s*radix_s + this->data[i - 1]);
  1090.   return this->sign*s;                // calculate sign
  1091. }
  1092.  
  1093.  
  1094.  
  1095. // operator int - conversion operator from CoolBignum to int
  1096. // Inputs:  none
  1097. // Outputs:  CoolBignum converted to int
  1098.  
  1099. CoolBignum::operator int () const {
  1100.   if (*this > max_int_s) {            // If int overflow
  1101.     overflow("operator int ()");        //   raise exception
  1102.   }
  1103.   if (*this < -max_int_s) {            // If int underflow
  1104.     underflow("operator int ()");        //   raise exception
  1105.   }
  1106.   int j = 0;                    // Otherwise, do conversion
  1107.   for (Counter i = this->count; i > 0; i--)    // For each data element
  1108.     j = int(j*radix_s + this->data[i - 1]);    //   stick it into j and shift
  1109.   return this->sign*j;                // Attach sign
  1110. }
  1111.  
  1112.  
  1113.  
  1114. // operator long - conversion operator from CoolBignum to long
  1115. // Inputs:  none
  1116. // Outputs:  CoolBignum converted to long
  1117.  
  1118. CoolBignum::operator long () const {
  1119.   if (*this > max_long_s) {            // If long overflow
  1120.     overflow("operator long ()");        //   raise exception
  1121.   }
  1122.   if (*this < -max_long_s) {            // If long underflow
  1123.     underflow("operator long ()");        //   raise exception
  1124.   }
  1125.   long l = 0;                    // Otherwise, do conversion
  1126.   for (Counter i = this->count; i > 0; i--)    // For each data element
  1127.     l = l*radix_s + this->data[i - 1];        //   stick it into l and shift
  1128.   return this->sign*l;                // Attach sign
  1129. }
  1130.  
  1131.  
  1132.  
  1133. // operator float - conversion operator from CoolBignum to float
  1134. // Inputs:  none
  1135. // Outputs:  CoolBignum converted to float
  1136.  
  1137. CoolBignum::operator float () const {
  1138.   if (*this > max_float_s) {            // If float overflow
  1139.     overflow("operator float ()");        //   raise exception
  1140.   }
  1141.   if (*this < -max_float_s) {            // If float underflow
  1142.     underflow("operator float ()");        //   raise exception
  1143.   }
  1144.   float f = 0.0;                // Otherwise, do conversion
  1145.   for (Counter i = this->count; i > 0; i--)    // For each data element
  1146.     f = f*radix_s + this->data[i - 1];        //   stick it into f and shift
  1147.   return this->sign*f;                // Attach sign
  1148. }
  1149.  
  1150.  
  1151.  
  1152. // operator double - conversion operator from CoolBignum to double
  1153. // Inputs:  none
  1154. // Outputs:  CoolBignum converted to double
  1155.  
  1156. CoolBignum::operator double () const {
  1157.   if (*this > max_double_s) {            // If double overflow
  1158.     overflow("operator double ()");        //   raise exception
  1159.   }
  1160.   if (*this < -max_double_s) {            // If double underflow
  1161.     underflow("operator double ()");        //   raise exception
  1162.   }
  1163.   double d = 0.0;                // Otherwise, do conversion
  1164.   for (Counter i = this->count; i > 0; i--)    // For each data element
  1165.     d = d*radix_s + this->data[i - 1];        //   stick it into d and shift
  1166.   return this->sign*d;                // Attach sign
  1167. }
  1168.  
  1169.  
  1170.  
  1171. // print --  terse print function for CoolBignums
  1172. // Inputs:   reference to output stream
  1173. // Outputs:  none
  1174.  
  1175. void CoolBignum::print (ostream& os) {
  1176.   os << "/* CoolBignum " << (long)this << " */";
  1177. }
  1178.  
  1179.  
  1180.  
  1181. // dump -- dump the contents of a CoolBignum to a stream
  1182. // Inputs:  stream to dump to (default cout)
  1183. // Outputs:  none
  1184.  
  1185. void CoolBignum::dump (ostream& os) {
  1186.   os << "{count: " << this->count <<        // output count field
  1187.         ", sign: " << this->sign  <<        // output sign field
  1188.         ", state: " << this->state <<        // output state field
  1189.     ", data: " << this->data <<        // output data pointer
  1190.     ", {";
  1191. #ifdef THE_OLD_WAY_USING_THAT_UGLY_FORM
  1192.   // format string == "%04X%s" or "%02X%s", etc.
  1193.   static char format_str[10] =
  1194.     {'%','0',char(2*sizeof(Data) + '0'),'X','%','s'};
  1195.   format_str[2] = char(2*sizeof(Data) + '0');
  1196.   if (this->count > 0) {            // output data array
  1197.     for (Counter i = this->count; i > 1; i--)
  1198.       os << form(format_str,this->data[i - 1],","); 
  1199.     os << form(format_str,this->data[0],"");
  1200.   }
  1201. #else // the new and improved way which probably no two compilers get alike
  1202.   if (this->count > 0) {            // output data array
  1203.     long save_flags = os.flags();         // save format state
  1204.     char save_fill = os.fill('0');        // use fill character
  1205.     int width = sizeof(Data)*CHAR_BIT/4;  // max width of data in hex
  1206.     for (Counter i = this->count; i > 1; i--)
  1207.       os << setw(width) << hex << this->data[i - 1] << ","; 
  1208.     os << setw(width) << hex << this->data[0];
  1209.     os.fill(save_fill);                   // reset fill character
  1210.     os.flags(save_flags);                 // rest format state (eg, dec)
  1211.   }
  1212. #endif
  1213.   os << "}}";                    // close brackets
  1214. }
  1215.  
  1216.  
  1217.  
  1218. // minus_infinity -- raise a minus infinity error exeption
  1219. // Inputs:  name of function in which exception occurred
  1220. // Outputs:  none
  1221.  
  1222. void CoolBignum::minus_infinity (const char* name) const {
  1223.   //RAISE (Error, SYM(CoolBignum), SYM(Minus_Infinity),
  1224.   printf ("CoolBignum::%s: Quotient is negative infinity.\n", name);
  1225.   abort ();
  1226. }
  1227.  
  1228.  
  1229.  
  1230. // plus_infinity -- raise a plus infinity error exception
  1231. // Inputs:  name of function in which exception occurred
  1232. // Outputs:  none
  1233.  
  1234. void CoolBignum::plus_infinity (const char* name) const {
  1235.   //RAISE (Error, SYM(CoolBignum), SYM(Plus_Infinity),
  1236.   printf ("CoolBignum::%s: Quotient is positive infinity.\n", name);
  1237.   abort ();
  1238. }
  1239.  
  1240.  
  1241.  
  1242. // divide_by_zero -- raise a division by zero error exception
  1243. // Inputs:  name of function in which exception occurred
  1244. // Outputs:  none
  1245.  
  1246. void CoolBignum::divide_by_zero (const char* name) const {
  1247.   //RAISE (Error, SYM(CoolBignum), SYM(Divide_By_Zero),
  1248.   printf ("CoolBignum::%s: Divide by zero.\n", name);
  1249.   abort ();
  1250. }
  1251.  
  1252.  
  1253.  
  1254. // overflow -- raise an overflow exception
  1255. // Inputs:  name of function in which exception occurred
  1256. // Outputs:  none
  1257.  
  1258. void CoolBignum::overflow (const char* name) const {
  1259.   //RAISE (Error, SYM(CoolBignum), SYM(Overflow),
  1260.   printf ("CoolBignum::%s: Overflow occured during type conversion.\n", name);
  1261.   abort ();
  1262. }
  1263.  
  1264.  
  1265.  
  1266. // underflow -- raise an underflow exception
  1267. // Inputs:  name of function in which exception occurred
  1268. // Outputs:  none
  1269.  
  1270. void CoolBignum::underflow (const char* name) const {
  1271.   //RAISE (Error, SYM(CoolBignum), SYM(Underflow),
  1272.   printf ("CoolBignum::%s: Underflow occured during type conversion.\n", name);
  1273.   abort ();
  1274. }
  1275.  
  1276.  
  1277.  
  1278. // no_conversion -- raise a no conversion exception
  1279. // Inputs:  name of function in which exception occurred
  1280. // Outputs:  none
  1281.  
  1282. void CoolBignum::no_conversion (const char* name) const {
  1283.   //RAISE(Error, SYM(CoolBignum), SYM(No_Conversion),
  1284.   printf ("CoolBignum::%s: Can not convert input parameter to CoolBignum.\n", name);
  1285.   abort ();
  1286. }
  1287.  
  1288.  
  1289. // end Bignum.C
  1290.